DP G
from dynamic programming
DP_G
G
The problem of finding the longest path in a graph
DP_G bad
1TLE
code:python
def solve(N, M, edges):
longest = -1 * (N + 1)
def get_longest(start):
if longeststart != -1:
return longeststart
next_edges = edges.get(start)
if not next_edges:
ret = 0
else:
ret = max(get_longest(v) for v in edgesstart) + 1
longeststart = ret
return ret
return max(get_longest(v) for v in edges)
Python 428 ms AC
code:python
def solve(N, M, edges):
longest = -1 * (N + 1)
for i in range(N + 1):
if not edgesi:
longesti = 0
def get_longest(start):
next = edgesstart
for v in next:
if longestv == -1:
longestv = get_longest(v)
ret = max(longestv for v in next) + 1
return ret
for i in range(N + 1):
if longesti == -1:
longesti = get_longest(i)
return max(longestv for v in edges)
Cython
https://atcoder.jp/contests/dp/submissions/14906046
---
This page is auto-translated from /nishio/DP G. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I'm very happy to spread my thought to non-Japanese readers.